package 题目集.动态规划.状压dp;

import java.util.Arrays;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/matchsticks-to-square/
 */
public class ch02_火柴拼正方形 {
	public boolean makesquare(int[] matchsticks) {
		maths = matchsticks;
		int sum = Arrays.stream(maths).sum();
		if (sum % 4 != 0)
			return false;
		limit = sum / 4;
		finalState = (1 << maths.length) - 1;
		Arrays.sort(matchsticks);
		return dfs(1, 0, 0);
	}

	int limit; // 每测最大长度
	int finalState; // 最终状态
	int[] maths;
	byte[] dp = new byte[1 << 16];
	static final int sideTotal = 4;

	public boolean dfs(int side, int len, int state) {
		if (dp[state] != 0)
			return dp[state] == 1;
		dp[state]=2;
		if(side==sideTotal+1) {	//4侧全选完了
			dp[state]=(byte) (state==finalState?1:2);
		}else {
			for (int i = maths.length - 1; i >= 0; i--) {
				int to = 1 << i;
				int nextLen = len + maths[i];
				if ((to & state) == 0 && nextLen <= limit) {
					int nextSide = nextLen == limit ? side + 1 : side;
					nextLen = nextLen == limit ? 0 : nextLen;
					if (dfs(nextSide, nextLen, to | state)) {
						dp[state] = 1;
						break;
					}
				}
			}
		}
		return dp[state] == 1;
	}

	@Test
	public void test() {
		int[] arr = { 5, 5, 5, 5, 16, 4, 4, 4, 4, 4, 3, 3, 3, 3, 4 };
		boolean res = makesquare(arr);
		System.out.println(res);
	}
}
